package com.lsa.iview.unsorted;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import com.lsa.helpers.ISimpleClosure;

public class SmallTasks {
	public static String removeSpacesInPlace(char[] s) {
		int srcIdx = 0;
		int dstIdx = 0;
		
		// PRE: dstIdx is the insertion point in the s. We only insert non-ws there.
		while(srcIdx < s.length) {
			if (!Character.isWhitespace(s[srcIdx])) {
				s[dstIdx] = s[srcIdx];
				dstIdx++;
			}
			srcIdx++;
		}
		if (dstIdx < s.length) {
			s[dstIdx] = 0;
		}
		return fromNullTerminated(s);
	}
	
	public static int countWords(String text) {
		int cnt = 0;
		boolean isInsideWordPrev = false;
		for (int i = 0; i < text.length(); i++) {
			boolean isInsideWordCur = !Character.isWhitespace(text.charAt(i));
			if (isInsideWordPrev && !isInsideWordCur) {
				cnt++;
			}
			isInsideWordPrev = isInsideWordCur;
		}
		if (isInsideWordPrev) {
			cnt++;
		}
		return cnt;
	}
	
	public static String putchar(int n) {
		StringBuilder sb = new StringBuilder();
		putchar(n, sb);
		return sb.toString();
	}
	
	private static void putchar(int n, StringBuilder sb) {
		int rem = n % 10;
		if (n > 10) {
			putchar(n / 10, sb);
		}
		
		sb.append((char)('0'+rem));
	}
	
	private static String fromNullTerminated(char[] s) {
		int i = 0;
		for (; i < s.length; i++) {
			if (s[i] == 0) break;
		}
		return new String(s, 0, i);
	}
	
	public static boolean isPalindrome(int n) {
		int p = 1;
		while (p * 10 < n)
			p *= 10;
	 
		while (n > 9 ) {
			int last = n % 10;
			int first= n / p;
			if (last != first )
				return false;
			n %= p;
			n /= 10;
			p /= 100;
		}
		return true;
	}
	
	public static void rotateInplace(int[] arr, int k) {
		int l = arr.length;

		k = k % l;
		if (k == 0){
			return;
		}

		int processed = 0;
		int idx = 0;
		int el = arr[idx];
		while(processed < arr.length) {
			int dst = (idx + k) % l;
			int newel = arr[dst];
			arr[dst] = el;
			el = newel;
			idx = dst;
			processed++;
		}
	}
	
	public static int[] rotate(int[] arr, int k) {
		k = k % arr.length;
		int[] newarr = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			newarr[(i+k) % arr.length] = arr[i];
		}
		return newarr;
	}
	
	public static int[] skippedProduct2(int[] arr) {
		int[] dp = new int[arr.length * 2];
		
		dp[0] = 1;
		dp[arr.length] = 1;
		
		for (int i = 1; i < arr.length; i++) {
			dp[i] = dp[i - 1] * arr[i - 1];
		}
		
		for (int i = 0; i < arr.length  - 1; i++) {
			dp[arr.length + 1 + i] = dp[arr.length + i] * arr[arr.length - 1 - i]; 
		}
		
		for (int i = 0; i < arr.length; i++) {
			arr[i] = dp[i] * dp[dp.length - 1 - i];
		}
		return arr;
	}
	
	public static int[] skippedProduct3(int[] arr) {
		int[] dp = new int[arr.length + 1 ];
		int[] res = new int[arr.length ];
		dp[0] = 1;
		dp[1] = arr[0];
		for (int i = 1; i < arr.length; i++) {
			dp[i+1] = arr[i] * dp[i];
		}
		int product = 1;
		for (int i = arr.length - 1; i > -1; --i) {
			res[i] = dp[i] * product;
			product *= arr[i];
		}
		return res;
	}
	
	public static int[] skippedProduct(int[] arr) {
		int[] res = new int[arr.length];
		Arrays.fill(res, 1);
		int left = 1;
		int right = 1;
		for (int i = 0; i < arr.length; i++) {
			res[i] *= left;
			res[arr.length - 1 - i] *= right;
			
			left *= arr[i];
			right *= arr[arr.length - 1 - i];
		}
		return res;
	}
	
	public static int[] skippedProductTest(int[] arr) {
		int n = arr.length;
		int[] newarr = new int[arr.length];
		for (int i = 0; i < n; i++) {
			newarr[i] = product(arr, 0, i - 1) * product(arr, i + 1, n - 1);
		}
		return newarr;
	}
	
	public static List<Integer> primes(int n) {
		List<Integer> primes = new ArrayList<Integer>();
		if (n < 1) {
			return primes;
		}
		for (int i = 2; i <= n; i++) {
			if (i == 2) {
				primes.add(i);
				continue;
			}
			int sqrt = (int)Math.sqrt(i);
			boolean isPrime = true;
			for (int j = 0; j < primes.size(); j++) {
				int p = primes.get(j);
				if (p <= sqrt) {
					if (i % p == 0) {
						isPrime = false;
						break;
					}
				}
				else {
					break;
				}
			}
			if (isPrime) primes.add(i);
		}
		
		return primes; 
	}
	
	private static int product(int[] arr, int from, int to) {
		if (from > to) return 1;
		
		int product = 1;
		for (int i = from; i <= to; i++) {
			product = product * arr[i];
		}
		
		return product;
	}
	
	public static void sumsToTarget(int target, int[] elements, ISimpleClosure<List<Integer>> resultCallback  ) {
		boolean[] solution = new boolean[elements.length];
		sumsToTarget(target, solution, -1, elements, resultCallback);
	}
	
	private static void sumsToTarget(int target, boolean[] solution, int solutionIdx, int[] elements, ISimpleClosure<List<Integer>> resultCallback  ) {
		if (target == 0) {
			List<Integer> result =  new ArrayList<Integer>();
			for (int i = 0; i < solution.length; i++) {
				if (solution[i]) {
					result.add(elements[i]);
				}
			}
			resultCallback.invoke(result);
		}
		else if (target > 0 && solutionIdx < elements.length - 1) {
			boolean[] sol1 = solution.clone();
			boolean[] sol2 = solution.clone();
			++solutionIdx;
			sol1[solutionIdx] = true;
			sol2[solutionIdx] = false;
			sumsToTarget(target - elements[solutionIdx], sol1, solutionIdx, elements, resultCallback);
			sumsToTarget(target, sol2, solutionIdx, elements, resultCallback);
		}
	}
	
	public static double pow(double x, int n) {
		double res = 1;
		double y = x;
		while(n > 0) {
			if ((n & 1) != 0) {
				res *= y;
			}
			n >>= 1;
			y *= y;
		}
		return res;
	}
	
	public static double pow_old(double x, int n) {
		if (n == 0) return 1;
		double res = x;
		int m = 1;
		for (m = 2; m < n; m <<= 1) {
			res *= res;
		}
		m >>= 1;
		
		for (int i = 0; i < n - m; i++) {
			res *= x;
		}
		
		return res;
	}
}

